using System;
using System.Collections;
using Deepcode.Flux.Core.Extensions.Codons;

namespace Deepcode.Flux.Core.Extensions
{
	/// <summary>
	/// Sorts a list of AddinTreeNode's based on their codon's insert before / after.
	/// </summary>
	public class CodonSorter
	{
		public AddinTreeNode [] Sort( Hashtable Original )
		{
			AddinTreeNode [] sortedNodes = new AddinTreeNode[ Original.Keys.Count ];
			// Visited will identify which have been processed
			Hashtable visited = new Hashtable( Original.Keys.Count );
			// Ancestors holds an arraylist for each item in the list and 
			// gets populated with the items that are created after itself.
			Hashtable ancestors = new Hashtable( Original.Keys.Count );
			// Initialise the lists we'll use to sort
			foreach( object key in Original.Keys )
			{
				visited[key] = false;
				ancestors[key] = new ArrayList();
			}
			// Loop over each item in the originals and populate the ancestors list.
			foreach(DictionaryEntry child in Original)
			{
				ICodon c = ((AddinTreeNode) child.Value).Codon;
				if( c == null ) continue;

				if( c.InsertAfter != null )
				{
					if( ancestors.Contains( c.InsertAfter ))
						((ArrayList) ancestors[c.InsertAfter]).Add( child.Key );
				}
				if( c.InsertBefore != null )
				{
					if( ancestors.Contains( child.Key ))
						((ArrayList) ancestors[child.Key]).Add( c.InsertBefore );
				}
			}

			// create the process keys array based on the original order
			object [] keyarray = new object[visited.Keys.Count];
			visited.Keys.CopyTo( keyarray, 0 );
			int index = keyarray.Length - 1;

			for (int i = 0; i < keyarray.Length; ++i) 
			{
				if((bool)visited[keyarray[i]] == false)
				{
					index = Visit(keyarray[i], Original, sortedNodes, 
						visited, ancestors, index);
				}
			}
			return sortedNodes;
		}

		private int Visit(object key, Hashtable nodes, AddinTreeNode [] sortedNodes, Hashtable visited, Hashtable anchestor, int index)
		{
			visited[key] = true;
			foreach (string anch in (ArrayList)anchestor[key]) 
			{
				if ((bool)visited[anch] == false) 
				{
					index = Visit(anch, nodes, sortedNodes, visited, anchestor, index);
				}
			}
			
			sortedNodes[index--] = (AddinTreeNode)nodes[key];
			return index;
		}

	}
}
